package algocasts;

import java.util.HashSet;
import java.util.Set;

public class P27_hasCycle {
    class ListNode {
        int val;
        ListNode next;
    }

    // Time:O(n)  Space:O(n)
    public boolean hasCycle_HashSet(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        for (ListNode p = head; p != null; p = p.next) {
            if (set.contains(head)) return true;
            else set.add(head);
        }
        return false;
    }

    // Time:O(n) Space:O(1)
    public boolean hasCycle_TwoPointer(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }
}
